算法设计与分析[0008] Dynamic Programming(I)（Unique Paths）

编程珠玑Algorithm

　本文通过 Unique Paths [I] & [II] 两道题从普通的递归思路到动态规划两种方式的求解尝试，希望能够初步分析如何根据动态规划的思路，进行问题求解。

Problem Description

  • 两道题解决的问题相似，都是求解从格网图左上角（Start）→ 右下角（Finish）可行的路径总数，而且行走方向只有向下或者向右移动两种方式，只是在以下两个地方存在一些区别：
    • Unique Paths [I] 行走的格网图不设立障碍，而 Unique Paths [[II] 中行走的格网图存在障碍，在可行路径选取上需要考虑避开障碍物的问题。
    • 由于上面的区别，导致在输入上两道题有所不同：前者只需要输入格网图的大小（#row*#column）；后者则需要提供格网图的0-1矩阵（1表示网格存在障碍物）

递归思想解答

  • 由于每一步的行走策略只有两种，不是向下走就是向右走，因此，假设当前这一步完成后到达右下角（#row，#column），那么只有（#row-1，#column）向下走和（#row，#column-1）向右走这两种方式，所以可行的路径总数显然就是从起点（1，1）到这两个中间点的可行路径总数之和。
  • 按照上述的思路，很容易通过递归的方式最终会退到起点（递归基），并通过递归函数返回得到总的可行路径数目。
  • 需要注意的一点是，由于每一步只有向右或者向下两种策略，所以，并不需要递归回起点（1，1），当回退到（1，？）或（？，1）时，从起点到当前中间点，有且只有一条路径（一直向右走或者一直想下走）。
  • Unique Paths [I] 按照递归思路的解答如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int uniquePaths(int m, int n) {
        // sanity check
        if(m<1 || n<1) {
            return 0;
        }
        // when m==1 or n==1, only directly down or directly right
        if(m==1 || n==1) {
            return 1;
        }
        
        // left to right + up to down
        return uniquePaths(m, n-1) + uniquePaths(m-1, n);
    }
};
  • Unique Paths [[II] 则需要进一步考虑当前步是否可行的问题，倘若存在障碍物，显然此路不通，不应计入可行路径的统计，return 0。
  • 另外，与 Unique Paths [I] 不同，只有回退到起点，才能判断通过递归历经的网格所构成的路径是可行的。因为，只是回退到（1，？）或（？，1），一旦起点到该中间点的向右直走路径或向下直走路径中间出现任何一个障碍物，该路径都是不可行的。
  • 以下是递归解答，留意与前一道题目在输入上的区别。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
private:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid, int m, int n) {
        if(obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }
        // obstacleGrid[0][0] == 0
        if(m==1 && n==1) {
            return 1;
        }
        // left to right
        if(m==1) {
            return uniquePathsWithObstacles(obstacleGrid, m, n-1);
        }
        // up to down
        if(n==1) {
            return uniquePathsWithObstacles(obstacleGrid, m-1, n);
        }
        // up to down + left to right
        return uniquePathsWithObstacles(obstacleGrid, m-1, n) + uniquePathsWithObstacles(obstacleGrid, m, n-1);
    }
    
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int rowSize = obstacleGrid.size();
        int colSize = obstacleGrid[0].size();
        
        // sanity check
        if((colSize < 1) || (obstacleGrid[0][0] == 1) || (obstacleGrid[rowSize-1][colSize-1] == 1)) {
            return 0;
        }
        
        return uniquePathsWithObstacles(obstacleGrid, rowSize, colSize);
    }
};
  • 递归思路解答对上述问题并不可行
    • 我们都知道，直接的递归实现，可读性强，但频繁的函数调用会造成一定的时间损耗，因此上述两题都存在 Time Limit Exceeded 的错误。
    • 另一个更为关键的问题是，上述简单的递归实现，每次递归的时候都对从起点到达当前中间网格的可行路径数进行了重复计算，这种重复计算的代价是巨大的，往往需要好几层回退；假如能够避免这种冗余，肯定会带来巨大的提升。

动态规划思路解答

  • 动态规划思路就能很好解决上述的问题：回退的方式不好避免重复计算的问题（可能需要维护从起点到达每个网格可行路径总数的表，另外通过是否为Inf避免重复计算，为了让每次递归均能访问操作该表，需要将其置为全局变量），我们干脆换个方向，从起点出发，直到到达右下角；动态规划的过程就像是在填上述这样一个表。
  • 通过递归回退+维护从起点到达每个网格可行路径总数的表避免冗余计算的方式（记忆化搜索），因为只有在右下角到起点的可行路径上的网格才会被计算，能够避开其他不必要的网格；但是，函数的调用显然有一定损耗。
  • 动态规划这种填表的思路，会将所有网格对应的表项填满，但这种顺序进行的操作实现简易（通过一个数组，两三层循环即可实现），耗时也较少，因此在大多数问题（动态规划多余的计算数目并不算多）下较记忆化搜索有一定优势。
  • Unique Paths [[II] 的动态规划解答关键已经在递归思路中体现，即：从起点到当前网格的可行路径总数为到左方网格（向右移动到达当前网格）及上方网格（向下移动达到当前网格）可行路径总数之和。
    • 需要注意的是，从起点到（1，？）或（？，1）的可行路径显然都只有一条（一直向右移动/一直向下移动）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int uniquePaths(int m, int n) {
        // sanity check
        if(m<1 || n<1) {
            return 0;
        }
        
        int paths[m][n];
        // paths(1, 1...n), left to right
        for(int col=0; col<n; col++) {
            paths[0][col] = 1;
        }
        // paths(1...n, 1), up to down
        for(int row=0; row<m; row++) {
            paths[row][0] = 1;
        }
        
        for(int row=1; row<m; row++) {
            for(int col=1; col<n; col++) {
                // left to right + up to down
                paths[row][col] = paths[row][col-1] + paths[row-1][col];
            }
        }
        
        return paths[m-1][n-1];
    }
};
  • Unique Paths [[II] 思路基本一致，只是当当前网格存在障碍物，其到起点的可行路径显然不存在。
    • 另外，对于从起点到（1，？）或（？，1）可行路径的分析与递归思路解答时一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int rowSize = obstacleGrid.size();
        int colSize = obstacleGrid[0].size();
        
        if((rowSize < 1) || (obstacleGrid[0][0] == 1) || (obstacleGrid[rowSize-1][colSize-1] == 1)) {
            return 0;
        }
        
        int paths[rowSize][colSize];
        // obstacleGrid[0][0] == 0 from above
        paths[0][0] = 1;
        
        // paths(1, 1...n)
        for(int col=1; col<colSize; col++) {
            paths[0][col] = obstacleGrid[0][col]==0 ? paths[0][col-1] : 0;
        }
        // paths(1...n, 1)
        for(int row=1; row<rowSize; row++) {
            paths[row][0] = obstacleGrid[row][0]==0 ? paths[row-1][0] : 0;;
        }
        
        for(int row=1; row<rowSize; row++) {
            for(int col=1; col<colSize; col++) {
                // left to right + up to down
                paths[row][col] = obstacleGrid[row][col]==0 ? (paths[row][col-1] + paths[row-1][col]) : 0;
            }
        }
        
        return paths[rowSize-1][colSize-1];
    }
};

本文标题:算法设计与分析[0008] Dynamic Programming(I)（Unique Paths）

文章作者:Gary

发布时间:2017-04-13, 14:00:22

最后更新:2020-03-28, 12:37:22

原始链接:http://durant35.github.io/2017/04/13/Algorithms_Dynamic Programming(I)/

文章目录
  1. 1. Problem Description
  2. 2. 递归思想解答
  3. 3. 动态规划思路解答